home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / µSim 1.1 / FabLibsƒ / FabWmemman.c < prev    next >
Encoding:
Text File  |  1997-05-04  |  7.8 KB  |  366 lines  |  [TEXT/CWIE]
  1. /*
  2. ANSI C _working_ equivalents for malloc, free, realloc, calloc;
  3. as a free bonus, you get ffcalloc() and fgetallocsize()
  4. unexplicably missing from the standard libraries.
  5.  
  6. malloc & free implementation based on Kernighan&Ritchie, 2nd ed.;
  7. realloc, calloc, ffcalloc, fgetallocsize by Fabrizio Oddone.
  8.  
  9. 2/1/95
  10. Modified the realloc routine in order to behave as described in
  11. section 7.10.3.4 of ANSI/ISO-C;
  12. that is:
  13. if ptr is a null pointer, realloc() allocates size bytes,
  14. else if size is 0, the memory block pointed to by ptr is freed.
  15. */
  16.  
  17.  
  18. //#include    <StdLib.h>
  19. #include    <String.h>
  20. #include    "UtilsSys7.h"
  21. #include    "FabWmemman.h"
  22.  
  23. //#pragma fourbyteints on
  24. //typedef long Align;
  25.  
  26. typedef union header Header;
  27.  
  28. union header {
  29.     struct {
  30.         Header *ptr;    // next block if on free list
  31.         size_t    size;        // size of this block (not bytes but MEMORY_UNITs)
  32.         } s;
  33.     };
  34.  
  35. //#define    USETEMPORARYMEMORY    1
  36. //#define    USE64BITUNITS    1
  37.  
  38. #ifdef    USE64BITUNITS
  39. #define    MEMORY_UNIT    sizeof(Header)
  40. #else
  41. #define    MEMORY_UNIT    4
  42. #endif
  43.  
  44. /* NALLOC determines the amount of memory asked to the Mac OS */
  45. /* the allocated block is then handled by malloc */
  46. /* currently morecore asks "at least 64Kbytes" (you may want smaller blocks) */
  47.  
  48. #define    NALLOC    (8192UL / MEMORY_UNIT)    // minimum # units to request
  49.  
  50.  
  51. static Header base;    // empty list to get started
  52. static Header *freep = NULL;    // start of free list
  53.  
  54. static Header *morecore(size_t nu);
  55.  
  56. static void makefree(void *bp);
  57. static size_t fgetallocsize(const void *p);
  58. static void NewMasterPointer(const void * const ld);
  59. static void DeleteMasterPointer(const void * const ld);
  60. static Boolean MasterPointerExists(const void * const ld);
  61.  
  62.  
  63. #define    HDR(p)    ((Header *)p)
  64.  
  65. void *fmalloc(size_t nbytes)
  66. {
  67. Ptr    p;
  68. Header *prevp;
  69. size_t    nunits, tempsize;
  70.  
  71. //DebugStr("\pNow entering fmalloc");
  72. nunits = (nbytes + sizeof(Header) - 1) / MEMORY_UNIT + 1;
  73. if ((prevp = freep) == NULL) {    // no free list yet
  74.     base.s.ptr = freep = prevp = &base;
  75.     base.s.size = 0;
  76.     }
  77.  
  78. for (p = (Ptr)prevp->s.ptr; ; prevp = HDR(p), p = (Ptr)HDR(p)->s.ptr) {
  79.     tempsize = HDR(p)->s.size;
  80.     if (tempsize >= nunits) {    // big enough
  81.         if (
  82. #ifdef    USE64BITUNITS
  83.         tempsize == nunits
  84. #else
  85.         tempsize <= nunits + 1
  86. #endif
  87.         )    // exactly
  88.             prevp->s.ptr = HDR(p)->s.ptr;
  89.         else {    // allocate tail end
  90.             HDR(p)->s.size -= nunits;
  91.             //p = (Header *)((Ptr)p + p->s.size * MEMORY_UNIT);
  92.             p += HDR(p)->s.size * MEMORY_UNIT;
  93.             HDR(p)->s.size = nunits;
  94.             }
  95.         freep = prevp;
  96.         return (p + sizeof(Header));
  97.         }
  98.     if (HDR(p) == freep)    // wrapped around free list
  99.         if ((p = (Ptr)morecore(nunits)) == NULL)
  100.             return NULL;    // none left
  101.     }
  102. }
  103.  
  104.  
  105. static Header *morecore(size_t nu)
  106. {
  107. Header *up;
  108.  
  109. if (nu < NALLOC)
  110.     nu = NALLOC;
  111.  
  112. ReserveMem(nu * MEMORY_UNIT);    // low in the heap
  113.  
  114. if (NULL == (up = (Header *)
  115. #ifdef USETEMPORARYMEMORY
  116.     NewHandleGeneral
  117. #else
  118.     NewHandle
  119. #endif
  120.         (nu * MEMORY_UNIT)))
  121.     return NULL;    // no space left
  122.  
  123. //#ifdef USETEMPORARYMEMORY
  124. HLock((Handle)up);
  125. up = (Header *)StripAddress(*(Handle)up);
  126. NewMasterPointer(up);
  127. //#endif
  128. up->s.size = nu;
  129. makefree(up + 1);
  130. return freep;
  131. }
  132.  
  133. void ffree(void *bp)
  134. {
  135. makefree(bp);
  136. bp = HDR(bp) - 1;    // point to block header
  137. if (MasterPointerExists(bp))
  138.     ReclaimMacOS_Idle();
  139. }
  140.  
  141. void makefree(void *bp)
  142. {
  143. Header *p, *tmp;
  144.  
  145. //(void) memset(bp, 255, fgetallocsize(bp));
  146.  
  147. bp = HDR(bp) - 1;    // point to block header
  148. // !(bp > p && bp < p->s.ptr)
  149. //for (p = freep; bp <= p || bp >= p->s.ptr; p = p->s.ptr)
  150. //    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
  151. //        break;    // freed block at start or end of arena
  152.  
  153. p = freep;
  154. tmp = p->s.ptr;
  155. while (bp <= p || bp >= tmp) {
  156.     if (p >= tmp && (bp > p || bp < tmp))
  157.         break;    // freed block at start or end of arena
  158.     p = p->s.ptr;
  159.     tmp = p->s.ptr;
  160.     }
  161.  
  162. if ((Ptr)bp + HDR(bp)->s.size * MEMORY_UNIT == (Ptr)tmp) {    // join to upper neighbor
  163.     HDR(bp)->s.size += tmp->s.size;
  164.     HDR(bp)->s.ptr = tmp->s.ptr;
  165.     }
  166. else
  167.     HDR(bp)->s.ptr = tmp;
  168. if ((Ptr)p + p->s.size * MEMORY_UNIT == (Ptr)bp) {    // join to lower neighbor
  169.     p->s.size += HDR(bp)->s.size;
  170.     p->s.ptr = HDR(bp)->s.ptr;
  171.     }
  172. else
  173.     p->s.ptr = bp;
  174. freep = p;
  175.  
  176. }
  177.  
  178. /* reallocates and copies the old block only when necessary */
  179.  
  180. void *frealloc(void *ap, size_t s)
  181. {
  182. Ptr    bp;
  183. Header *p, *new_block;
  184. void *r = ap;
  185. size_t    cursize, nunits, temp;
  186.  
  187. if (ap) {
  188.     if (s) {
  189.         bp = (Ptr)ap - sizeof(Header);
  190.         nunits = (s + sizeof(Header) - 1) / MEMORY_UNIT + 1;
  191.         cursize = HDR(bp)->s.size;
  192.         if (nunits
  193. #ifndef    USE64BITUNITS
  194.             + 1
  195. #endif
  196.             < cursize) {
  197. // trim only if the remaining space is enough to form a "zero-length" block
  198. // (a block consisting of the header and nothing else, that is).
  199.             HDR(bp)->s.size = nunits;
  200.             bp += nunits * MEMORY_UNIT;
  201.             HDR(bp)->s.size = cursize - nunits;
  202.             makefree(bp + sizeof(Header));
  203.             }
  204.         else if (nunits > cursize) {
  205.             for (p = freep; !(bp > (Ptr)p && bp < (Ptr)p->s.ptr); p = p->s.ptr)
  206.                 if (p >= p->s.ptr && (bp > (Ptr)p || bp < (Ptr)p->s.ptr))
  207.                     break;    // freed block at start or end of arena
  208.             temp = p->s.ptr->s.size + cursize;
  209.             if ((bp + cursize * MEMORY_UNIT == (Ptr)p->s.ptr) && (temp >= nunits)) {
  210. // we can expand the block upwards in memory
  211.                 if (
  212. #ifdef    USE64BITUNITS
  213.                 temp == nunits
  214. #else
  215.                 temp <= nunits + 1
  216. #endif
  217.                 ) {
  218. // there is an adjacent free block matching exactly our needs
  219.                     HDR(bp)->s.size = temp;
  220.                     p->s.ptr = p->s.ptr->s.ptr;
  221.                     }
  222.                 else {
  223. // we need to split the adjacent block
  224.                     new_block = (Header *) (bp + nunits * MEMORY_UNIT);
  225.                     new_block->s.ptr = p->s.ptr->s.ptr;
  226.                     new_block->s.size = temp - nunits;
  227.                     HDR(bp)->s.size = nunits;
  228.                     p->s.ptr = new_block;
  229.                     }
  230.                 freep = p;
  231.                 }
  232.             else {
  233.         // expanding not possible; reallocate, copy and free the old block
  234.                 if (r = fmalloc(s)) {
  235.                     //BlockMoveData(ap, r, cursize * MEMORY_UNIT - sizeof(Header));
  236.                     (void) memcpy(r, ap, cursize * MEMORY_UNIT - sizeof(Header));
  237.                     ffree(ap);
  238.                     }
  239.                 }
  240.             }
  241.         }
  242.     else {
  243.         ffree(ap);
  244.         r = NULL;
  245.         }
  246.     }
  247. else
  248.     r = fmalloc(s);
  249.  
  250. return r;
  251. }
  252.  
  253. size_t fgetallocsize(const void *ap)
  254. {
  255. return ((Header *)ap - 1)->s.size * MEMORY_UNIT - sizeof(Header);
  256. }
  257.  
  258. void *fcalloc(size_t nelem, size_t nsize)
  259. {
  260. void *p;
  261. size_t    nbytes = nelem * nsize;
  262.  
  263. if (p = fmalloc(nbytes)) {
  264. // memset used to be poorly implemented…
  265. //    MyZeroBuffer(p, numOfLongs(nbytes + 3));
  266.     (void) memset(p, 0, nbytes);
  267.     }
  268. return p;
  269. }
  270.  
  271. void *ffcalloc(size_t s)
  272. {
  273. void *p;
  274.  
  275. if (p = fmalloc(s)) {
  276. // memset used to be poorly implemented…
  277. //    MyZeroBuffer(p, numOfLongs(s + 3));
  278.     (void) memset(p, 0, s);
  279.     }
  280. return p;
  281. }
  282.  
  283.  
  284. void ReclaimMacOS_Idle(void)
  285. {
  286. Header    *hp, *tmp;
  287. Handle    h;
  288.  
  289. hp = freep;
  290. tmp = hp->s.ptr;
  291. do {
  292.     if (MasterPointerExists((Ptr)tmp)) {
  293. //Debugger();
  294.         h = RecoverHandle((Ptr)tmp);
  295.         if (noErr == MemError()) {
  296.             if (InlineGetHandleSize(h) == tmp->s.size * MEMORY_UNIT) {
  297.                 hp->s.ptr = tmp->s.ptr;    // eliminate from free list
  298.                 DeleteMasterPointer((Ptr)tmp);
  299.                 tmp = hp->s.ptr;
  300.                 DisposeHandle(h);
  301.                 freep = hp;
  302.                 continue;
  303.                 }
  304.             }
  305.         }
  306.     hp = tmp;
  307.     tmp = hp->s.ptr;
  308.     } while (hp != freep);
  309. }
  310.  
  311.  
  312. enum {
  313. kInitialSlots = 16
  314. };
  315.  
  316. static Handle    gMParr = nil;
  317. static int    gMPcount = 0, gMPmaxcount = kInitialSlots;
  318.  
  319. void NewMasterPointer(const void * const ld)
  320. {
  321.  
  322. if (gMParr == nil) {
  323.     gMParr = NewHandle(sizeof(Ptr) * kInitialSlots);
  324.     }
  325. else if (gMPcount == gMPmaxcount) {
  326.     gMPmaxcount += kInitialSlots;
  327.     SetHandleSize(gMParr, sizeof(Ptr) * gMPmaxcount);
  328.     }
  329.  
  330. ((Ptr *)(*gMParr))[gMPcount++] = ld;
  331. }
  332.  
  333. void DeleteMasterPointer(const void * const ld)
  334. {
  335. Ptr        *deref;
  336. int        i;
  337. int        newCount;
  338.  
  339. deref = (Ptr *)*gMParr;
  340. // find window in array
  341. for (i = 0; i < gMPcount; i++)
  342.     if (ld == deref[i]) {
  343. // move items
  344.         newCount = gMPcount - 1;
  345.         if (i != newCount)
  346.             (void) memmove(&deref[i], &deref[i+1], (newCount - i) * sizeof(Ptr));
  347.         gMPcount = newCount;    // updated last to avoid concurrency problems
  348.         break;
  349.         }
  350. }
  351.  
  352. Boolean MasterPointerExists(const void * const ld)
  353. {
  354. Ptr        *deref;
  355. int        i;
  356.  
  357. deref = (Ptr *)*gMParr;
  358. // find window in array
  359. for (i = 0; i < gMPcount; i++)
  360.     if (ld == deref[i]) {
  361.         return true;
  362.         }
  363. return false;
  364. }
  365.  
  366.